package org.algorithm.YaYa.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;

/**
 * 区间链表反转
 * @author jiazhaoxin
 * @Date 2022/2/12
 * @Desc {https://leetcode-cn.com/problems/reverse-linked-list-ii/}
 * 先将 curr 的下一个节点记录为 next；
 * 执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
 * 执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
 * 执行操作 ③：把 pre 的下一个节点指向 next。
 *
 */
public class 反转链表2 {

    public static void main(String[] args){
        ListNode node = ListNode.build(1,2,3,4,5);
        ListNode res = reverseList2(node,2,4);
        System.out.println(ListNode.print(res));

    }

    public static ListNode reverseList2(ListNode head, int m, int n) {
        // 设置 虚拟节点是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < n - m; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;

    }
}
